package solution;

/**
 * <a href="https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e?tpId=188&&tqId=38590&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC109 岛屿数量</a><br/>
 * <span color="orange">搞嘛, 本地jdk11 答案正确; 牛客网jdk8就不行</span>
 *
 * @author or2
 * @Description 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
 * 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
 * @create 2021年09月03日 时间: 10:47
 */
public class NumsOfIsland {
    /**
     * 判断岛屿数量
     *
     * @param grid char字符型二维数组
     * @return int整型
     */
    public int solve(char[][] grid) {
        int nLength = grid.length;
        int mLength = grid[0].length;
        int maxLength = nLength * mLength;
        int[] parent = new int[maxLength];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        int ans = maxLength;

        for (int i = 1; i < nLength; i++) {
            if (grid[0][i] == 1) {
                if (grid[0][i - 1] == 1) {
                    ans += unionElements(getIndex(mLength, 0, i - 1), getIndex(mLength, 0, i), parent);
                }
            } else {
                ans--;
            }
        }
        for (int i = 1; i < mLength; i++) {
            if (grid[i][0] == 1) {
                if (grid[i - 1][0] == 1) {
                    ans += unionElements(getIndex(mLength, i - 1, 0), getIndex(mLength, i, 0), parent);
                }
            } else {
                ans--;
            }
        }

        for (int i = 1; i < nLength; i++) {
            for (int j = 1; j < mLength; j++) {
                if (grid[i][j] == 1) {
                    if (grid[i - 1][j] == 1) {
                        ans += unionElements(getIndex(mLength, i - 1, j), getIndex(mLength, i, j), parent);
                    }
                    if (grid[i][j - 1] == 1) {
                        ans += unionElements(getIndex(mLength, i, j - 1), getIndex(mLength, i, j), parent);
                    }
                } else {
                    ans--;
                }
            }
        }

        return ans;
    }

    /**
     * 将二维矩阵下标 转化为 并查集下标
     *
     * @param mLength 一维数组元素的长度
     * @param nIndex  原数组一维下标
     * @param mIndex  原数组二维下标
     * @return 并查集中的下标
     */
    private int getIndex(int mLength, int nIndex, int mIndex) {
        return nIndex * mLength + mIndex;
    }

    /**
     * 并查集查找操作
     *
     * @param pIndex 在并查集中的下标
     * @param parent 并查集
     * @return 所属集合标识
     */
    private int find(int pIndex, int[] parent) {
        while (pIndex != parent[pIndex]) {
            pIndex = parent[pIndex];
        }
        return pIndex;
    }

    /**
     * 在并查集中 下标为 p 与下标为 q 的元素是否在同一集合中
     *
     * @param p      在并查集中的下标
     * @param q      在并查集中的下标
     * @param parent 所属并查集
     * @return 属于同意集合 -> true<br/>否则 -> false
     */
    private boolean isConnected(int p, int q, int[] parent) {
        return parent[p] == parent[q];
    }

    /**
     * 并查集 - 合并集合操作
     *
     * @param p      并查集中元素
     * @param q      并查集中元素
     * @param parent 并查集
     * @return 出现合并返回 -1<br/>否则返回 0
     */
    private int unionElements(int p, int q, int[] parent) {
        int pRoot = find(p, parent);
//        优化, 使子节点直接指向最终结点
        parent[p] = pRoot;
        int qRoot = find(q, parent);
        parent[q] = qRoot;

        if (pRoot == qRoot) {
            return 0;
        }

        parent[pRoot] = qRoot;
        return -1;
    }
}
